package interview;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class interview_08_08 {
    public String[] permutation(String S) {
        List<String> list=new LinkedList<>();
        boolean[] flag=new boolean[S.length()];
        search(list,flag,S,new StringBuilder());
        String[] result=new String[list.size()];
        for(int i=0;i<list.size();++i){
            result[i]=list.get(i);
        }
        return result;
    }
    public void search(List<String> list,boolean[] flag,String S,StringBuilder stringBuilder){
        if(S.length()==stringBuilder.length()){
            list.add(stringBuilder.toString());
            return;
        }
        HashSet<Character> set=new HashSet<>();
        for(int i=0;i<S.length();++i){
            if(!flag[i]&&!set.contains(S.charAt(i))){
                flag[i]=true;
                stringBuilder.append(S.charAt(i));
                search(list, flag, S, stringBuilder);
                stringBuilder.deleteCharAt(stringBuilder.length()-1);
                flag[i]=false;
                set.add(S.charAt(i));
            }
        }
    }
}
